/**
 * @author LKQ
 * @date 2021/12/4 18:03
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.climbStairs1(10));
    }

    public int climbStairs(int n) {
        // 通过数学归纳法可以得出 f(n) = f(n-1) + f(n-2) 为著名的斐波那契数列。
        if (n <=2) {
            return n;
        }else {
            return climbStairs(n-1) + climbStairs(n-2);
        }
        // 虽然这是最直白的递归，但是无法AC，原因是n一旦偏大，将超出时间限制，该方法被pass。
    }
    public int climbStairs1(int n) {
        // 无法直接递归，那么可以用滚动数组思想, 每次循环将n减1, 那么时间复杂度为O(n)
        // p q r
        // 0 0 1
        // 0 1 1
        // 1 1 2
        // 1 2 3
        // 2 3 5
        int p = 0, q = 0, r = 1;
        while (n > 0) {
            p = q;
            q = r;
            r = p + q;
            n--;
        }
        return r;
    }

    public int climbStairs2(int n) {
        // 当n再变大时，O(n)的时间复杂度同样高，使用数学方法矩阵快速幂来优化到O(logN)时间复杂度
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }

    public int climbStairs3(int n) {
        // 根据斐波那契数列的通项公式来直接计算
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) Math.round(fibn / sqrt5);
    }

}
